package bm7;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/7/20 18:44
 * BM7.链表中环的入口节点
 * https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=295&tqId=605&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    // 快慢指针思路
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 边界处理
        if (pHead == null || pHead.next == null) {
            return null;
        }
        // 先利用快慢指针找到相遇的节点
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        // 如果 fast = null, 说明没有环
        if (fast == null) {
            return null;
        }
        // 此时 slow == fast 为相遇的节点
        // 让 slow 回到头节点, 与 fast 步差为 0 迭代, 找到相遇的点即为入口节点
        slow = pHead;
        while (fast != null && slow != null && slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    private static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
